package sort.onlogn.my_quick_sort_test;

import java.util.Arrays;

/**
 * @author yeyangtao created at 10:55 2020/12/21
 */
public class QuickSort1221 {
    public static void main(String[] args) {
        int[] a = new int[]{2, 3, 9, 0, 4, 7, 69, 4, 3, 7, 6, 97, 9, 73, 49, 6, 76};
        quickSort(0, a.length - 1, a);
        System.out.println(Arrays.toString(a));
    }

    private static void quickSort(int left, int right, int[] a) {
        if (left >= right) return;
        int p = partition(left, right, a);
        quickSort(left, p - 1, a);
        quickSort(p + 1, right, a);
    }

    private static int partition(int left, int right, int[] a) {
        int pivot = a[right];
        int i = left;
        for (int j = left; j <= right; j++) {
            if (a[j] < pivot) {
                if (i == j) {
                    i++;
                } else {
                    int temp = a[i];
                    a[i++] = a[j];
                    a[j] = temp;
                }
            }
        }
        a[right] = a[i];
        a[i] = pivot;
        return i;
    }
}
